home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / MISC / HEXAGON1.ZIP / HEXAGON1.TXT
Encoding:
Text File  |  1997-01-10  |  8.0 KB  |  265 lines
  1.  
  2.  
  3. Article: 8616 of rec.games.programmer
  4.  
  5. >Does anyone have an insights and/or algorithms for resolving x,y mouse
  6. >hits on a hex grid?
  7.  
  8. Say your grid is enumerated like this:
  9.     __    __    __
  10.    /03\__/24\__/45\
  11.    \__/13\__/34\__/
  12.    /02\__/23\__/44\
  13.    \__/12\__/33\__/
  14.    /01\__/22\__/43\
  15.    \__/11\__/32\__/
  16.    /00\__/21\__/42\
  17.    \__/  \__/  \__/
  18.  
  19. and say that the origin is the bottom left corner of the 00 hexagon.
  20. I'll use Warwick Allison's parameters also:
  21.  
  22.         (mx,my) = mouse coordinate
  23.         h = height of hexagon
  24.         tw = width of hexagon horizontal side
  25.         cw = width of side triangle
  26.  
  27.  -- = cw
  28.    ____
  29.   /    \    |
  30.  /      \   | = h
  31.  \      /   |
  32.   \____/    |
  33.  
  34.    ---- = tw
  35.  
  36. Then we can divide the region into cw+tw x h sized rectangles in a
  37. sideways brick-layer's pattern so that the rectangles are almost in the
  38. same place as the hexagons:
  39.  
  40.    _______     ______
  41.   /|   \ |    /|   \ |
  42.  / |01  \|_____|22  \|
  43.  \ |    /|   \ |    /|
  44.   \|___/_|11  \|___/_|
  45.   /|   \ |    /|   \ |
  46.  / |00  \|___/_|21  \|
  47.  \ |    /|   \ |    /|
  48.   \|___/_|    \|___/_|
  49.  
  50. The idea is to assume first that if the mouse landed in rectangle ij
  51. then it landed in hexagon ij and then correct if the mouse position is
  52. in one of the two triangular flaps.  I'll compute two numbers tx and ty
  53. which index the hexagon that the user clicked in.  All my arithmetic is
  54. in integers and I assume that division is never rounded up, and,
  55. compatibly, remainders are always non-negative.  I also assume h, the
  56. height of a hexagon, is even.  Here's the code:
  57.  
  58. tx = mx/(cw+tw); rx = mx%(cw+tw);
  59. my += tx*h/2;
  60. ty = my/h; ry = my%h;
  61. rx = tw+cw-rx;
  62. ry -= h/2;
  63. if(2*cw*ry > rx*h) {tx++; ty++;}
  64. if(2*cw*ry < -rx*h) tx++;
  65.  
  66.  
  67. Article: 8688 of rec.games.programmer
  68.  
  69. Here's an old post that I wrote up a while ago.  It deals with
  70. dividing the game map into triangles and doing hit-testing.
  71. There are ways to increase the speed of the routines, and
  72. the math gets easier if you adopt another numbering scheme,
  73. but the routines here are tested and used with my MS Windows
  74. hexmap editing program.
  75. Updates to this posting, with faster computations, would be nice.
  76. We should make a FAQ on this subject.
  77.  
  78. Routines to convert from (x,y) coordinate to Hex sheet numbering.
  79.  
  80.  
  81. I. Background and definition
  82.  
  83.  
  84. I am writing a computerized version of the Task Force StarFire
  85. game, using Actor, which is a smalltalk-like environment running
  86. under Microsoft Windows.  The syntax of Actor is similar to C.
  87. I will try to put the routines in C-like format for this posting.
  88.  
  89.  
  90. These routines could best be used as hit-testing for mouse
  91. clicks. Given an (x,y) mouse position, it will give you the hex
  92. label.  I also use it to find neighboring hexes, taking the
  93. center of the hex my starship is in, adding one unit of distance
  94. at the current angle I am facing, and finding the label of that
  95. hex.  That way my dialog boxes can give all information in hex
  96. numbers so the program is easy to use with maps.  Note that the
  97. center to center (x,y) distance is NOT the same as the number of
  98. hexes between two points distance.  Hex 1014 is 18 hexes from hex
  99. 0101, but only about 15.5 units in (x,y) space.  I wrote a
  100. routine that 'counts' the hexes between two hexes, and I'll
  101. include that at the end.
  102.  
  103.  
  104. The map I am working with is layed out like this:
  105.  
  106.  
  107.           _____         _____         _____
  108.          /*    \  0200 /     \  0400 /     \
  109.         /  0101 \_____/ 0301  \_____/  0501 \
  110.         \       /     \       /     \       /
  111.          \_____/  0201 \_____/  0401 \_____/
  112.          /     \       /     \       /     \
  113.         /  0102 \_____/  0302 \_____/  0502 \
  114.         \       /     \       /     \       /
  115.          \_____/  0202 \_____/  0402 \_____/
  116.  
  117.  
  118. and the cartesian (x,y) coordinates I use have (0,0) at the upper
  119. left corner of hex 0101 (at the *), with x increasing to the
  120. right, and y increasing downward.  One distance of 1 in the (x,y)
  121. system is defined as the inter-hex center to center distance,
  122. also equal to the smallest diameter of the hexagon.
  123.  
  124.  
  125. II. Algorithm
  126.  
  127.  
  128. The algorithm is a two step process. I could collapse the two
  129. steps into one large formula, but I thought you'd like to
  130. understand how I got it.
  131.  
  132.  
  133. I create three new axis, centered on the (x,y) origin.  The H-
  134. axis runs vertically (the same as the y axis).  The E-axis is a
  135. line sloping upwards at +30 deg.  The X-axis (sorry about the use
  136. of the same letter) runs downwards at -30 deg.  Given an (x,y)
  137. point, I project the vector from the origin to the point onto
  138. each axis and record the length of the projection. I then take
  139. that length, double it (to make the math easier), and truncate
  140. towards negative infinity (Careful, since int(-4.12) = -4.  I use
  141. instead the floor() function. i.e. floor(3.42) = 3, floor(-4.12)
  142. = -5, floor(-3) = -3 ).  This gives me a tripple (H,E,X) which
  143. places the point within a triangle on the board.  If you draw the
  144. three axis, and draw perpidicular lines to them at 1/2 unit
  145. intervals, it will divide the board up like this:
  146.  
  147.  
  148.        Hex 0101          (H,E,X) inside each triangle.
  149.        ____________
  150.       /\          /\                   Every triangle in the
  151.      /  \  0,0,0 /  \                  same row has the same
  152.     /    \      /    \                 H value, every triangle
  153.    /      \    /      \                 along the \ direction has
  154.   / 0,-1,0 \  / 0,0,1  \    Hex 0201      the same E value, and
  155.  /__________\/__________\____________      every triangle along
  156.  \  1,-1,0  /\  1,0,1  //\   1,1,2  /\      the / direction has
  157.   \        /  \       //  \        /  \      the same X value.
  158.    \      /    \     //    \      /    \
  159.     \    /      \   //      \    /      \
  160.      \  / 1,-1,1 \ // 1,0,2  \  /  1,1,3 \
  161.       \/__________\/__________\/__________\
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168. So once I've converted from (x,y) to (H,E,X) it is just a matter
  169. of calculating which hex a given (H,E,X) triangle is in.  Any
  170. triangle can be described by the following equation:
  171.  
  172.  
  173. <triangle> = <base> + n * < 0, 3, 3> + k * < 1, 1, 2>
  174.  
  175.  
  176. where I've defined <base> to be one of <0,-1,0>, <0,0,0>,
  177. <0,0,1>, <0,1,1>, <0,1,2>, or <0,2,2>.  The hex number is then a
  178. straight-forward function of <base>, n, and k.
  179.  
  180.  
  181. III. Functions
  182.  
  183.  
  184. I've grouped the functions as follows: utilities (basic math
  185. functions your library should have); (x,y) to <H,E,X>
  186. conversions; <H,E,X> to 0X0Y hex numbers; and the reverse:
  187. 0X0Y to the (x,y) point at the center of the hex;
  188.  
  189.  
  190. III.1  utilities
  191.         Your compiler should have a function like floor(x), that
  192. takes a real number and returns the largest integer less than x.
  193. The correct results to check are:
  194.  floor(3.4)=3, floor(-3.2)=-4, and floor(-3.0) = -3.
  195. The last one gets screwed up by rounding sometimes.  If you don't
  196. have such a function, here's the code I used:
  197.  
  198.  
  199. usage:    J = floor(x);
  200.  
  201.  
  202. int floor(x)
  203. { if x >= 0
  204.   then return int(x);
  205.   else return int(x - 1 + 1E-10);
  206.   endif;
  207. };
  208. Where I added the 1E-10 to make float(-3.0) = -3.  If you make
  209. this number too small, you won't have enough digits of precision
  210. to make it matter.
  211.  
  212.  
  213. III.2 (x,y) to <H,E,X> routines
  214.  
  215.  
  216. usage:  H = get_H(_xcoord, _ycoord)
  217.  
  218.  
  219. int get_H(_xcoord, _ycoord)
  220. float _xcoord, _ycoord;
  221. {
  222.   return floor( 2.0 * y);
  223. }
  224.  
  225.  
  226. int get_E(_xcoord, _ycoord)
  227. float _xcoord, _ycoord;
  228. {
  229.  return floor( sqrt(3.0) * _xcoord - _ycoord);
  230. }
  231.  
  232.  
  233. int get_X(_xcoord, _ycoord)
  234. float _xcoord, _ycoord;
  235. {
  236.  return floor( sqrt(3.0) * _xcoord + _ycoord);
  237. }
  238.  
  239.  
  240. III.3 (x,y) to hexnumber, using above routines
  241.  
  242.  
  243. usage:  hexnum = getHex( _xcoord, _ycoord);
  244.  
  245.  
  246. where hexnum is a 4 digit decimal number, such as 0101 or 2013,
  247. corresponding to the hex map numbering.
  248.  
  249.  
  250. int getHex(_xcoord, _ycoord)
  251. float _xcoord, _ycoord;
  252. {
  253.   int t,n,ox,oy,h,e,x;
  254.  
  255.  
  256.   h = get_H(_xcoord, _ycoord);
  257.   e = get_E(_xcoord, _ycoord);
  258.   x = get_X(_xcoord, _ycoord);
  259.  
  260.  
  261.   /* t will be the E value of the <base> triangle */
  262.   t := e + h - x + ((((x-2*h) mod 3)+3) mod 3);
  263.  
  264.  
  265.   /* <hex> = <base> + n*<0,3,3> + get_H()*<1,1,2> */
  266.